Dénombrement en informatique

Lien Moodle : https://moodle.epita.fr/mod/page/view.php?id=99493

Contenu du cours

Dans le cadre de vos cours d'algorithmique, vous avez déjà fait face à quelques problèmes qu'on qualifie de dénombrement. Pour l'essentiel ce sont des problèmes dit de complexité (en temps). Étant donné un programme informatique $P$ il s'agit de compter le nombre d'opérations coûteuse que celui-ci effectue au cours de son exécution, pour une entrée de taille fixée. Par exemple, si $P$ est un programme qui vérifie qu'une liste est croissante, on s'intéressera au nombre d'opérations de comparaison que $P$ effectue, pour une liste de taille $n$ . Voici quelques exemples classiques de dénombrement auxquels vous avez déjà été confrontés ou que vous observerez prochainement au cours de vos études :

le calcul du nombre de comparaisons lors de l'exécution d'un algorithme de recherche d'un élément dans une liste triées de taille $n$
le calcul du nombre de comparaisons lors de l'exécution d'un algorithme de tri d'une liste de taille $n$
le calcul du nombre de comparaisons lors de la recherche d'un sous-mot dans un mot contenant $n$ caractères
le calcul du nombre d'appels lors de l'exécution d'une fonction récursive pour une entrée de taille $n$
le calcul du nombre de mots de passe de taille $k$ qu'on peut générer à partir d'un alphabet de taille $n$
le calcul du nombre de mots de passe de taille $k$ et n'ayant aucun caractère en commun qu'on peut générer à partir d'un alphabet de taille $n$ .

Certains de ces calculs ont des réponses explicites (les deux derniers par exemple), pour d'autres on ne peut y répondre lisiblement qu'en clarifiant la situation à l'étude. Par exemple, quand on cherche un élément dans une liste doit-on considérer le cas où cet élément s'y trouve ou celui où il ne s'y trouve pas? Dans chacun de ces cas, on se ramène à un problème de dénombrement pour lequel on est en mesure d'apporter une réponse explicite. Les éléments de raisonnement et les savoir-faire nécessaires à la résolution de ces problèmes sont ceux abordés dans ce MiMo. On se limite dans cette première interaction avec le dénombrement à des problèmes relativement aseptisés, des problèmes qui nécessitent peu de redéfinition du contexte, l’interaction entre la théorie du dénombrement et l'étude asymptotique de complexité sera notamment vue plus tardivement.